#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <search.h>

#define DEBUG_LOG(fmt, args...) sprintf(stdout, fmt, ##args)
#define DEBUG_LOG_1(fmt, ...) sprintf(stdout, fmt, ##__VA_ARGS__)

void *root = NULL;

void *xmalloc(unsigned n)
{
    void *p;
    p = malloc(n);
    if (p)
        return p;
    fprintf(stderr, "insufficient memory\n");
    exit(EXIT_FAILURE);
}

int compare(const void *pa, const void *pb)
{
    return (*(int *)pa - *(int *)pb);
#if 0
    if (*(int *) pa < *(int *) pb)
        return -1;
    if (*(int *) pa > *(int *) pb)
        return 1;
    return 0;
#endif
}

void action(const void *nodep, const VISIT which, const int depth)
{
    int *datap;

    switch (which) {
        case preorder:
            break;
        case postorder:
            datap = *(int **) nodep;
            printf("%6d\n", *datap);
            break;
        case endorder:
            break;
        case leaf:
            datap = *(int **) nodep;
            printf("%6d\n", *datap);
            break;
    }
}

int main(void)
{
    int i, *ptr, pfind;
    void *val;
    int sample[16] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };

    srand(time(NULL));
    for (i = 0; i < sizeof(sample)/sizeof(sample[0]); i++) {
        ptr = xmalloc(sizeof(int));
        *ptr = sample[i];
        val = tsearch((void *) ptr, &root, compare);
        if (val == NULL)
            exit(EXIT_FAILURE);
        else if ((*(int **) val) != ptr)
            free(ptr);
    }
    pfind = 17;
    val = tfind((void *)&pfind, &root, compare);
    if (NULL == val)
    twalk(root, action);
    tdestroy(root, free);

    exit(EXIT_SUCCESS);
}

#if 0
int main(void)
{
    int i, *ptr;
    void *val;

    srand(time(NULL));
    for (i = 0; i < 12; i++) {
        ptr = xmalloc(sizeof(int));
        *ptr = rand() & 0xff;
        val = tsearch((void *) ptr, &root, compare);
        if (val == NULL)
            exit(EXIT_FAILURE);
        else if ((*(int **) val) != ptr)
            free(ptr);
    }
    twalk(root, action);
    tdestroy(root, free);

    exit(EXIT_SUCCESS);
}
#endif

